package com.zofer.study.sort;

import java.util.Arrays;

/**
 * @description 快速排序 O(n*logn)  最坏时间复杂度O(n²)
 * @date: 2020/10/27 11:04
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {4,1,7,5,8,6,2,0};
        System.out.println("排序前的数组:"+Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println("排序后的数组:"+Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int start,int end){
        if (start > end){
            return;
        }

        int i = start;
        int j = end;
        //基准数
        int b = arr[start];

        while (i < j){

            while (b <= arr[j] && i < j){
                j--;
            }

            while (b >= arr[i] && i < j){
                i++;
            }

            //如果满足条件则交换
            if (i < j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }

        //将基准位置和i=j的位置交换
        arr[start] = arr[i];
        arr[i] = b;

        //递归
        quickSort(arr,start,j-1);
        quickSort(arr,j+1,end);

    }
}
